/*
leetcode 141: 环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 
为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
 

提示：
链表中节点的数目范围是 [0, 10^4]
-105 <= Node.val <= 10^5
pos 为 -1 或者链表中的一个 有效索引 。
 
进阶：你能用 O(1)（即，常量）内存解决此问题吗？

解法：快慢指针法
*/
#include <iostream>
#include <vector>

// 定义链表节点
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (head == nullptr) return false;

        ListNode *slow = head;  // 慢指针
        ListNode *fast = head;  // 快指针

        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;             // 慢指针走一步
            fast = fast->next->next;       // 快指针走两步

            if (slow == fast) {
                return true;  // 如果快慢指针相遇，说明链表有环
            }
        }
        
        return false;  // 如果快指针到达末尾，说明没有环
    }
};

// 辅助函数，用于创建链表并测试
ListNode* createLinkedList(std::vector<int>& values) {
    if (values.empty()) return nullptr;
    
    ListNode* head = new ListNode(values[0]);
    ListNode* current = head;
    for (int i = 1; i < values.size(); ++i) {
        current->next = new ListNode(values[i]);
        current = current->next;
    }
    
    return head;
}

int main() {
    // 创建一个链表示例
    std::vector<int> values = {3, 2, 0, -4};  // 链表：3 -> 2 -> 0 -> -4
    ListNode* head = createLinkedList(values);
    
    // 让链表形成环
    head->next->next->next = head->next;  // 让最后一个节点指向第二个节点，形成环
    
    Solution solution;
    bool result = solution.hasCycle(head);  // 检查链表是否有环
    
    if (result) {
        std::cout << "yes" << std::endl;
    } else {
        std::cout << "no" << std::endl;
    }

    return 0;
}

